Stack & Queue by Example

Stats

3,531 visits, 4,641 views

Translations

This tutorial hasn't been translated.

Tools

STACK

In computer science, a stack or LIFO (last in, first out) is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the last element that was added.[1]

The term LIFO stems from the fact that, using these operations, each element "popped off" a stack in series of pushes and pops is the last (most recent) element that was "pushed into" within the sequence. This is equivalent to the requirement that, considered as a linear data structure, or more abstractly a sequential collection, the push and pop operations occur only at one end of the structure, referred to as the top of the stack. (Additionally, a peekoperation may give access to the top.)

(https://en.wikipedia.org/wiki/Stack_(abstract_data_type)).

QUEUE

In computer science, a queue is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure. . In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed. Often a peek or front operation is also entered, returning the value of the front element without dequeuing it. A queue is an example of a linear data structure, or more abstractly a sequential collection. (https://en.wikipedia.org/wiki/Queue_(abstract_data_type))

EXAMPLE

To make sure that you’re clear with the explanation above, we’re gonna make a simple experiment about how they work. What we’re trying to do is to reverse this descending stack to ascending.

You know that a stack an only be accessed from the top. So it’s not possible to re-arrange it using a simple loop. To solve it, we need to use a queue to acts as a buffer, which temporary store stack’s values, and then send them back to the stack.

First, create the stack. You can also push it dynamically using loop.

Second, push queue from stack’s top (front), and pop the stack afterwards. Do it stack.width times.

Third, move back the value to stack. Push stack with queue’s front, and pop the queue afterwards. Do it queue.width times.

DONE! Your stack is now | 1 | 2 | 3 | 4 | 5 | from top to bottom.

You can download the file

here

also like my fanpage to get more tutorials.

  • 0 Comments

  • Order by
Want to leave a comment? Login or Register an account!