Skip to main content

STACK

Quick reference

Worst Case
spaceO(n)
pushO(1)
popO(1)
peekO(1)

stack stores items in a last-in, first-out (LIFO) order.

Picture a pile of dirty plates in your sink. As you add more plates, you bury the old ones further down. When you take a plate off the top to wash it, you're taking the last plate you put in. "Last in, first out."

Strengths:

  • Fast operations. All stack operations take O(1) time.

Uses:

  • The call stack is a stack that tracks function calls in a program. When a function returns, which function do we "pop" back to? The last one that "pushed" a function call.
  • Depth-first search uses a stack (sometimes the call stack) to keep track of which nodes to visit next.
  • String parsing—stacks turn out to be useful for several types of string parsing.

Implementation

You can implement a stack with either a linked list or a dynamic array—they both work pretty well:

Stack PushStack Pop
Linked Listsinsert at headremove at head
Dynamic Arraysappendremove last element

Java comes with a built in stack implementation , but it's better to use Deques instead.

The stack implementation has a few big drawbacks: it doesn't have an interface and it extends the Vector class, which has thread synchronization overhead.

Comments

Popular posts from this blog

SQL - Part 1

SQL tutorial from scratch -- Part 1


                                                            Introduction


Before going deep dive into in SQL I want to explain the main purpose of DB(database).
Suppose we have large amount of data (for example it would be the students in the same class), and we want to create some website which is give us all information about them. How we do it. Of course using database.Maybe you ask yourself questions: "I can store them in file or array". Yes you is exactly right. But imagine you have large amount of data and if you store them in file or array your program/website will work very hard. Now let's visualize databases:





As we can see it is one of the basic db type which is store title, release_year, length and replacement_cost.

Don't worry about DB if you don't understand them very well. Our next paragraphs will explain it more accurately and also I try to add some important images.






                    "Yes I know that right …

A simple calculator for adding and subtracting in c++

A simple calculator for adding and subtracting in c++











In this post, I write a code about very simple calculator in c++. Actually it is the problem in e-olymp.com
If you're not familiar with this website then you can go below link:
https://www.e-olymp.com/en/problems/7411


Input is in this form : 

                                             x+5=2  or 1+x=4  or  1+4=x
In the output we give the value of x.

It has very simple solution. That's why i give there only code and when you read this code line-by-line you easily understand it     :)

Solution:


#include<iostream>#include<string>using namespace std;int main(){ string statement;cin>>statement; int last_number = 0; if(statement[statement.length()-1] == '0' || statement[statement.length()-1] == '1'|| statement[statement.length()-1] == '2' || statement[statement.length()-1] == '3'|| statement[statement.length()-1] == '4' || statement[statement.length()-1] == '…

Java Proqramlashdirma Dili

1) Dostlar bu blogda java proqramlasdirma dili haqqinda melumat verecyik

Java proqramlasdirma dili high level programming language sinfine daxildir bu proqramlasdirma dili muxtelif platformalarda calisirki bu da onun ustun cehetlerinden biridir. Java proqramladirma diline oxshar dillere misal olaraq C, C#, C++ misal gostermek olar. Bunu qeyd etmek kifayetdir ki eger siz sadaladigim dillerden hec olmasa birini mukemmel bilsez o biri diller sizin ucun su kimi asan olar. Yeni esas sizin OOP den basiniz cixmalidir birdeki alqoritmleri derinden menisemek lazimdir. Eger alqoritmleri derinden menimsemek isteyirsinizse sizin sade riyazi biliklerden basinziz cixmalidir eks halda alqoritme geldikde sizin ucun cetin ola biler. Lakin size sad xeberim var, hetta riyzi bilikleriniz o qeder de yaxi deyilse de siz oz alqortim biliklerinizi tekmillesdir bilersiniz bunun ucun her movzudaki alqoritmlere aid coxlu mesele, misal hell etmek ve partnyorunuzla muzakire etmelisiniz . Bu muzakire etmek meseles…