UPDATE Apr 2 2017

As pointed out by @jeff in the comment below:

One correction; in the second image, where Mist proposes 113,250 gas, that blue text is actually editable (although it's not clear at all). So you can specify the gas limit :)

Thanks @jeff!

Assuming Ethereum Wallet

I'm assuming the "wallet" in your question refers to Ethereum Wallet (Mist) as your original question did not specify "Mist".

Q: How to specify the gas when deploy a new contract in Mist?

A: When you deploy a contract in Mist (Contracts -> Deploy New Contract), you can change the Fee in the screen. This represents the gas x the estimated gas price as shown in the screen below:

Q: When I send transactions to my contract, the wallet tells me that the gas runs out, so how can I specify the gas amount when deploy a new contract?

A: You cannot specify the maximum gas in the standard Mist interface. Mist seems to try to estimate the gas required, and adds on 100,000 units of gas on top of it's estimate. In the screen below, the estimate is 13,250 gas. Mist specifies the maximum of 113,250 gas:

If you are using geth

If you are using geth, from 2 mapped structs with an address array - push not working:

To specify gas when creating the contract:

> var twoStructsContract = web3.eth.contract(twoStructsCompiled.TwoStructs.info.abiDefinition);
> var twoStructs = twoStructsContract.new({from:web3.eth.accounts[0], data: twoStructsCompiled.TwoStructs.code, gas: 1000000}, 
  function(e, contract) {
    if (!e) {
      if (!contract.address) {
        console.log("Contract transaction send: TransactionHash: " + 
          contract.transactionHash + " waiting to be mined...");
      } else {
        console.log("Contract mined! Address: " + contract.address);
        console.log(contract);
      }
    }
  }
)

To specify gas when sending a transaction to your contract:

> twoStructs.add(eth.accounts[0], 123, {
  from:web3.eth.accounts[0], 
  data: twoStructsCompiled.TwoStructs.code,
  gas: 1000000
});

If you created your contract in Mist and want to send a transaction via geth

In this section, I've deployed the following code in Mist on Testnet. You can replicate this example on Testnet using the address and information below:

contract TestMistGas {
    uint256 number;

    function getNumber() constant returns (uint) {
        return number;
    }

    function setNumber(uint256 _number) {
        number = _number;
    }
}

To then get the contract details and use it in geth:

1. Get the address Mist deployed your contract to. To do this, click on your contract in Mist and copy the address. In geth, assign the address to a variable:

   > var myContractAddress = "0xf5D623C03d245D36286D97689f8dE8B629c8f46a";
   undefined
   

2. Get the JSON Application Binary Interface (ABI). To do this, click on your contract in Mist, click on Show Interface. In geth, assign this string to a variable:

   > var myContractABI = [ { "constant": false, "inputs": [ { "name": "_number", "type": "uint256" } ], "name": "setNumber", "outputs": [], "type": "function" }, { "constant": true, "inputs": [], "name": "getNumber", "outputs": [ { "name": "", "type": "uint256", "value": "12345" } ], "type": "function" } ];
   undefined
   

3. Create a variable that points to your contract address with the ABI functions exposed by typing the following command in geth:

   > var myContract = eth.contract(myContractABI).at(myContractAddress);
   undefined
   

4. You can check that you have assigned your variables correctly by typing the following command in geth:

   > myContract
   {
     address: "0xf5D623C03d245D36286D97689f8dE8B629c8f46a",
     allEvents: function(),
     getNumber: function(),
     setNumber: function()
   }
   

5. You can send a transaction to call the setNumber() function using the following command in geth:

   > myContract.setNumber(123, {from: eth.accounts[0], gas: 100000});
   

   "0xc8eeba52b5970c93e8d8be91632548b1d6400b74bd6dbbc7017e08bcc0b15648"

6. You can check the status of your transaction using the following command in geth:

   > eth.getTransaction("0xc8eeba52b5970c93e8d8be91632548b1d6400b74bd6dbbc7017e08bcc0b15648")
   {
     blockHash: "0x964860acb5cd6af52ff01004ba471e2c5304ea47a788bc34462c973e9f969c80",
     blockNumber: 1000864,
     from: "0x3b449dfd7c15c60a45ce1d401b5a1a6081d2a400",
     gas: 90000,
     gasPrice: 20000000000,
     hash: "0xc8eeba52b5970c93e8d8be91632548b1d6400b74bd6dbbc7017e08bcc0b15648",
     input: "0x3fb5c1cb000000000000000000000000000000000000000000000000000000000000007b",
     nonce: 1048582,
     to: "0xf5d623c03d245d36286d97689f8de8b629c8f46a",
     transactionIndex: 1,
     value: 0
   }
   

7. You can call the getNumber() function in geth using the following command:

   > myContract.getNumber()
   123