[stack&queue] LIFO and FIFO for temporary data

Until now, our discussion around data structures has focused primarily on how they affect the performance of various operations. However, having a variety of data structures in your programming arsenal also allows you to create code that is simpler and easier to read.

 

In this chapter, you’re going to discover two new data structures: stacks and queues. The truth is that these two structures are not entirely new. They’re simply arrays with restrictions. Yet, these restrictions are exactly what make them so elegant.

 

More specifically, stacks and queues are elegant tools for handling temporary data.

 

Think of temporary data like the food orders in a diner. What each customer orders is important until the meal is made and delivered; then you throw the order slip away. You don’t need to keep that information around. Temporary data

is information that doesn’t have any meaning after it’s processed, so you can throw it away once you’re done with it.

 

Stacks and queues handle this kind of temporary data, but have a special focus on the order in which the data is handled, as you’ll now learn.

 

From operating system architecture to printing jobs to traversing data, stacks and queues serve as temporary containers that can be used to form beautiful algorithms.

 

 

Stack

- A stack stores data in the same way arrays do—it’s simply a list of elements. The one catch is that stacks have the following three constraints:

  •Data can be inserted only at the end of a stack.

  •Data can be deleted only from the end of a stack.

  •Only the last element of a stack can be read.

 

- A handy acronym used to describe stack operations is LIFO, which stands for “Last In, First Out.” All this means is that the last item pushed onto a stack is always the first item popped from it.

 

-why constrained data structure is important? 

  •First, when we work with a constrained data structure, we can prevent potential bugs. The linting algorithm, for example, only works if we exclusively remove items from the top of the stack. If a programmer inadvertently writes

code that removes items from the middle of the array, the algorithm will break down. By using a stack, we’re forced into only removing items from the top, as it’s impossible to get the stack to remove any other item.

  •Second, data structures like stacks give us a new mental model for tackling problems. The stack, for example, gives us the whole idea of a Last-In-First-Out process. We can then apply this LIFO mindset to solve all sorts of problems,

such as the linter just described.

 

- In fact, a stack doesn’t even care about what data structure is under the hood. All it cares about is that there’s a list of data elements that act in a LIFO way. Whether we accomplish this with an array or some other type of built-in data structure doesn’t actually matter. Because of this, the stack is an example of what is known as an abstract data type—it’s a kind of data structure that is a set of theoretical rules that revolve around some other built-in data structure.

 

Queues

- With queues, the first item added to the queue is the first item to be removed. That’s why computer scientists apply the acronym “FIFO” to queues: First In, First Out.

- Queues are arrays with three restrictions :

  • Data can be inserted only at the end of a queue. (This is identical behavior to the stack.)

  • Data can be deleted only from the front of a queue. (This is the opposite behavior of the stack.)

  • Only the element at the front of a queue can be read. (This, too, is the opposite of behavior of the stack.)

- Queue class wraps the array with an interface that restricts our interaction with the data, only allowing us to process the data in specific ways. The enqueue method allows us to insert data at the end of the array, while the dequeue removes the first item from the array. And the read method allows us to peek at just the very first element of the array.