Shulou(Shulou.com)06/01 Report--

This article mainly explains "how to implement Java stack and queue". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to implement Java stack and queue.

1. Implement a circular queue

[OJ link]

Circular queues are generally implemented through arrays. We need to solve a few problems.

(1) the array subscript realizes the loop.

A, the subscript is last followed (offset is less than array.length): index = (index + offset)% array.length. To be more popular, if our array size is 8, the subscript goes to 7, and then how to return to 0, we can (index+1) 8 to achieve.

B, before the subscript, let's make a special judgment and set it to the size of the array minus one.

(2) distinguish between full and empty queues.

We can reserve a place for the array, if rear+1=front, the queue is full; if rear=front, the queue is empty. In this case, we need to consider the queue size, which needs to be one year larger than the original one when defining the array size.

[code as follows]

Class MyCircularQueue {public int front; public int rear; public int [] array; / / Construction method public MyCircularQueue (int k) {/ / the size of the array should be defined as KF1 this.array=new int [KF1];} / / queue public boolean enQueue (int value) {if (isFull ()) {return false because of the reserved position. } this.array [this.rear] = value; this.rear= (this.rear+1)% this.array.length; return true;} / / outbound public boolean deQueue () {if (isEmpty ()) {return false;} this.front= (this.front+1)% this.array.length; return true } / / get public int Front () {if (isEmpty ()) {return-1;} return this.array [front];} / / get public int Rear () {if (isEmpty ()) {return-1;} int index=-1 at the end of the line If (this.rear==0) {index=this.array.length-1;} else {index=this.rear-1;} return this.array [index];} / / determine whether it is empty public boolean isEmpty () {if (this.front==this.rear) {return true;} return false } / / determine whether the queue is full public boolean isFull () {if ((this.rear+1)% this.array.length==this.front) {return true;} return false;}} 2, queue implementation stack

[OJ link]

Because the first-in-first-out principle of the stack and the first-in-first-out principle of the queue. We need two queues to implement the stack. When both queues are empty, the stack is empty.

Push: it doesn't matter if you enter the stack for the first time. Both queues are empty, so you can choose any one to join the queue. When you enter the stack, there must be a queue that is not empty. Find a queue that is not empty and join the queue.

Out of the stack (pop): first of all, the stack is empty, can not carry out the stack operation; when the stack is not empty, there must be a queue listed as empty (queue1), a queue is not empty (queue2), the queue1 in the size-1 elements out of the stack into the queue2 (especially note that the queue1 size function can not be put into the loop, queue dequeue operation, its size is changed), and finally the last element in queue1 out of the queue is the return value.

Get the top element of the stack (top): it's similar to getting out of the stack, so I won't go into details.

[code as follows]

Class MyStack {private Queue queue1; private Queue queue2; / / constructor public MyStack () {queue1=new LinkedList (); queue2=new LinkedList ();} / stacked public void push (int x) {if (! queue2.isEmpty ()) {queue2.offer (x);} else {queue1.offer (x) }} / / out-of-stack public int pop () {if (empty ()) {return-1;} if (queue1.isEmpty ()) {int size=queue2.size (); for (int iTuno ()

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.