Data Structures: Stacks and Queues

Data Structures: Stacks and QueuesAngelo AcebedoBlockedUnblockFollowFollowingJan 19Stacks and queues are two types of dynamic data structures that you can use to store and retrieve data in different ways.

Stacks have a last-in-first-out mechanism (LIFO), while Queues have a first-in-first-out mechanism (FIFO).

But what does this mean?Stacks (LIFO)Stacks can be compared to piles of plates.

When you have a whole pile of plates, the only place you can add a new place is on top of the pile, aka the top of the stack.

The last plate you put on top is also the same plate that first gets out, hence the LIFO (last-in-first-out) mechanism.

The 2 most important methods in a stack are push() and pop().

Push() adds a new item to the top of the stack, and pop() removes the item at the top of the stack.

Just like a stack of plates, you can only push() an item in order from the last item, and you can only pop() from the top of the stack — aka, the last plate.

Stack ImplementationAll stacks require only one pointer looking to the end of the stack.

Whenever a push() or pop() operation is performed, the pointer should always increment/decrement to the last item of the stack.

For push(), the stack pointer will always increment to the index of the new element being “pushed.

”For pop(), the stack pointer will always decrement to the index of the element before the element being “popped.

”stack_pointer increments by 1 when “pushing” onto the stackstack_pointer decrements by 1 when “popping” from the stackNote that pop() doesn’t take any parameters, but push() does.

This is because pop() removes the last element no matter what, while push() adds an element, which means you’ll need to specify an element to add.

When dealing with stacks in code, there are some considerations to take:underflow: an exception will be thrown if popping from an empty stackoverflow: account for resizing the stack implementation when pushing to a full array.

Think back again on the analogy of a stack as a pile of plates.

The more plates you pile on top of each other, the first plate to get removed will always be the last plate you put on.

Hence, the plate that’s always on top is the first to get removed.

Queues (FIFO)http://rowiescribbles.

blogspot.

com/2013/04/malaysian-passport-renewal-online.

htmlThe 2 most important functions in a queue are dequeue() and enqueue().

The function dequeue() removes the first element of a queue, and enqueue() “pushes” an element to the end of the queue.

“dequeue()” from the front, “enqueue()” to the back.

The first element you enqueue() is the first element to be removed, hence the FIFO (first-in-first-out) mechanism.

Disclaimer: dequeue() can sometimes be referred to as pop(), but for the sake of consistency and to avoid confusion with the pop() function for stacks, I will refer to it as dequeue().

Queue ImplementationA common implementation of a queue is with Doubly Linked Lists, so we will use that data structure to analyze the handling of pointers.

Each element of the queue will be referred to as a Node.

Just like stacks, queues in a Doubly Linked List contain a pointer referring to the most recent item.

The only difference is that queues require 2 pointers looking to the beginning and end of the queue to take advantage of the dequeue() and enqueue() functions.

Once you enqueue() a node to the queue, the back_pointer increments by 1.

However, dequeue() is a lot trickier than enqueue().

This is because once you remove from the front of the queue, you’d have to deallocate the memory from the previous node and make the pointers account for the new size of the queue.

So once you dequeue() an element from the front of the queue, the front_pointer moves to point to the next node while retaining the same location in the Linked List, and you deallocate the space for the first node.

In effect, the back_pointer decrements by 1 to account for the new size.

Element 10 disappears, front_pointer changes reference to next node, back_pointer decrements by 1It is easy to think of a queue as a line of people.

To enqueue() means that more people are falling into the back of the line, and dequeue() means that the person who got there first, no matter who they are, will be let through first.

No matter how large the queue is, the person who arrives first will always be the first to leave.

Queues can also be thought of as a “first come, first serve” type of data structure, where deletion and insertion happen on different ends.

ConclusionsStacksStacks have a LIFO(last-in-last-out) structure, where deletion and insertion happen at the same end.

Stacks have 1 pointer looking to the end (“top”) of the stack.

Stacks use pop() and push() functions — removing and adding elements to the top of the stack.

QueuesQueues have a FIFO (first-in-first-out) structure, where deletion and insertion happen at opposite ends.

Queues have 2 pointers looking to the front and back of the queue.

Queues use enqueue() and dequeue() functions — adding to the end of the queue and removing from the front of the queue.

SourcesStack Data Structure – GeeksforGeeksA Computer Science portal for geeks.

It contains well written, well thought and well explained computer science and…www.

geeksforgeeks.

orgQueue Data Structure – GeeksforGeeksA Computer Science portal for geeks.

It contains well written, well thought and well explained computer science and…www.

geeksforgeeks.

orgStacks and QueuesThis textbook provides an interdisciplinary approach to the CS 1 curriculum.

We teach the classic elements of…introcs.

cs.

princeton.

eduImplementation of Deque using doubly linked list – GeeksforGeeksDeque or Double Ended Queue is a generalized version of Queue data structure that allows insert and delete at both…www.

geeksforgeeks.

org.. More details

Leave a Reply